Graph Traversal Techniques: BFS (Breadth-First Search), DFS (Depth-First Search) গাইড ও নোট

গ্রাফ ট্র্যাভার্সাল টেকনিকস: BFS (Breadth-First Search), DFS (Depth-First Search)

গ্রাফ ট্র্যাভার্সাল হল এমন একটি প্রক্রিয়া যার মাধ্যমে একটি গ্রাফের সবগুলো নোড বা শীর্ষ (vertex) পরিদর্শন করা হয়। দুটি প্রধান গ্রাফ ট্র্যাভার্সাল টেকনিক হল BFS (Breadth-First Search) এবং **DFS (Depth-First Search)**। এই দুটি টেকনিক গ্রাফের শীর্ষগুলো পরিদর্শন করার জন্য ভিন্ন ভিন্ন পদ্ধতি ব্যবহার করে।

1. BFS (Breadth-First Search)

BFS একটি গ্রাফ ট্র্যাভার্সাল অ্যালগরিদম যা স্তরভিত্তিক (level-wise) গ্রাফের নোড পরিদর্শন করে। অর্থাৎ, BFS প্রথমে এক্সপ্লোর করে একটি নোডের সমস্ত নিকটবর্তী (adjacent) নোডগুলো এবং তারপর একে একে পরবর্তী স্তরের নোডগুলো পরিদর্শন করে।

BFS এর কাজের প্রক্রিয়া:

• BFS একটি queue (কিউ) ব্যবহার করে। শুরুতে একটি শীর্ষ (vertex) কিউতে ঢোকানো হয়।
• কিউ থেকে একটি শীর্ষ নেয়া হয়, এবং তার সমস্ত প্রতিবেশী শীর্ষ কিউতে যুক্ত করা হয় যদি তারা আগে থেকে পরিদর্শিত না হয়ে থাকে।
• এই প্রক্রিয়া তখন পর্যন্ত চলতে থাকে যতক্ষণ না কিউ শূন্য হয়ে যায়।

BFS-এর সি প্রোগ্রামিং ভাষায় ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 5

int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 1, 0, 1},
    {1, 0, 0, 1, 0}
};

void bfs(int start) {
    bool visited[MAX_VERTICES] = {false};
    int queue[MAX_VERTICES], front = 0, rear = 0;
    
    queue[rear++] = start;
    visited[start] = true;

    printf("BFS Traversal: ");
    
    while (front < rear) {
        int current = queue[front++];
        printf("%d ", current);

        for (int i = 0; i < MAX_VERTICES; i++) {
            if (adjMatrix[current][i] == 1 && !visited[i]) {
                visited[i] = true;
                queue[rear++] = i;
            }
        }
    }
    printf("\n");
}

int main() {
    bfs(0); // Starting from vertex 0
    return 0;
}

Output:

BFS Traversal: 0 1 4 2 3 

BFS এর সুবিধা:

• BFS সর্বনিম্ন স্তরের নোডগুলি প্রথমে পরিদর্শন করে।
• সেরা পথ বা সর্বনিম্ন সংযোগের সমস্যাগুলোর জন্য উপকারী।

2. DFS (Depth-First Search)

DFS একটি গ্রাফ ট্র্যাভার্সাল অ্যালগরিদম যা গ্রাফের একটি শাখার শেষ পর্যন্ত চলে যায় এবং তারপর অন্য শাখায় চলে যায়। DFS প্রথমে একটি নোড নির্বাচন করে, এবং যতদূর সম্ভব তার একটি শাখায় চলে যায়, তারপর ফিরে এসে অন্য শাখায় চলে যায়।

DFS এর কাজের প্রক্রিয়া:

• DFS একটি stack (স্ট্যাক) ব্যবহার করে। এটি একটি নোড থেকে শুরু করে তার যতটা সম্ভব গভীরে যায়, তারপর সেই শাখা শেষ হলে একে একে পূর্ববর্তী শাখায় ফিরে আসে এবং পরবর্তী শাখায় চলে যায়।
• DFS সাধারনত পুনরাবৃত্তি (recursion) অথবা স্ট্যাক ব্যবহার করে বাস্তবায়িত হয়।

DFS-এর সি প্রোগ্রামিং ভাষায় ইমপ্লিমেন্টেশন:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define MAX_VERTICES 5

int adjMatrix[MAX_VERTICES][MAX_VERTICES] = {
    {0, 1, 0, 0, 1},
    {1, 0, 1, 0, 0},
    {0, 1, 0, 1, 0},
    {0, 0, 1, 0, 1},
    {1, 0, 0, 1, 0}
};

void dfs(int start, bool visited[MAX_VERTICES]) {
    visited[start] = true;
    printf("%d ", start);

    for (int i = 0; i < MAX_VERTICES; i++) {
        if (adjMatrix[start][i] == 1 && !visited[i]) {
            dfs(i, visited);
        }
    }
}

int main() {
    bool visited[MAX_VERTICES] = {false};
    printf("DFS Traversal: ");
    dfs(0, visited); // Starting from vertex 0
    printf("\n");
    return 0;
}

Output:

DFS Traversal: 0 1 2 3 4 

DFS এর সুবিধা:

• DFS সাধারণত গভীরতা অনুসরণ করে কাজ করার জন্য ডিপার্টমেন্টাল ডেটা গঠনের জন্য উপযুক্ত।
• এটি সাইকেল চিহ্নিতকরণ, সংযোগ উপাদান অনুসন্ধান এবং ট্রি গঠন সহ বিভিন্ন ক্ষেত্রে ব্যবহৃত হয়।

BFS এবং DFS এর মধ্যে পার্থক্য:

সারসংক্ষেপ:

• BFS এবং DFS দুটি জনপ্রিয় গ্রাফ ট্র্যাভার্সাল টেকনিক যা বিভিন্ন ধরনের সমস্যা সমাধান করতে ব্যবহৃত হয়।
• BFS হল একটি স্তরভিত্তিক পরিদর্শন পদ্ধতি, যেখানে সর্বপ্রথম নিকটবর্তী নোডগুলো পরিদর্শন করা হয় এবং DFS একটি গভীরতার অনুসরণকারী পদ্ধতি, যেখানে প্রতিটি শাখার গভীরে চলে যায়।
• দুইটি পদ্ধতিই গ্রাফের সব নোড পরিদর্শন করতে সক্ষম এবং তাদের নিজস্ব সুবিধা এবং প্রয়োগ রয়েছে, যেমন BFS সর্বনিম্ন পথের জন্য এবং DFS সাইকেল শনাক্তকরণের জন্য আদর্শ।